//给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
//
// 如果树中有不止一个众数，可以按 任意顺序 返回。
//
// 假定 BST 满足如下定义：
//
//
// 结点左子树中所含节点的值 小于等于 当前节点的值
// 结点右子树中所含节点的值 大于等于 当前节点的值
// 左子树和右子树都是二叉搜索树
//
//
//
//
// 示例 1：
//
//
//输入：root = [1,null,2,2]
//输出：[2]
//
//
// 示例 2：
//
//
//输入：root = [0]
//输出：[0]
//
//
//
//
// 提示：
//
//
// 树中节点的数目在范围 [1, 10⁴] 内
// -10⁵ <= Node.val <= 10⁵
//
//
//
//
// 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 612 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
//? 额外空间
function findMode(root: TreeNode | null): number[] {

    if (root === null) return [];
    const countMap: Map<number, number> = new Map();
    function traverse(root: TreeNode | null): void {
        if (root === null) return;
        countMap.set(root.val, (countMap.get(root.val) || 0) + 1);
        traverse(root.left);
        traverse(root.right);
    }
    traverse(root);
    const countArr: number[][] = Array.from(countMap);
    countArr.sort((a, b) => {
        return b[1] - a[1];
    })
    const resArr: number[] = [];
    const maxCount: number = countArr[0][1];
    for (let i of countArr) {
        if (i[1] === maxCount) resArr.push(i[0]);
    }
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
//? 递归中直接解决
function findMode2(root: TreeNode | null): number[] {
    let preNode: TreeNode | null = null;
    let maxCount: number = 0;
    let count: number = 0;
    let resArr: number[] = [];
    function traverse(root: TreeNode | null): void {
        if (root === null) return;
        traverse(root.left);
        if (preNode === null) { //? 第一个节点
            count = 1;
        } else if (preNode.val === root.val) {
            count++;
        } else {
            count = 1;
        }
        if (count === maxCount) {
            resArr.push(root.val);
        } else if (count > maxCount) {
            maxCount = count;
            resArr.length = 0;
            resArr.push(root.val);
        }
        preNode = root;
        traverse(root.right);
    }
    traverse(root);
    return resArr;
};
